The present invention relates generally to computer processing, and more particularly to techniques for detecting and processing cache hits for queries with aggregates.
Decision support systems are commonly available to assist businesses make proper decisions based on data that may be available from a myriad of different data sources. For example, analytics applications are available to simplify data analysis for specific business or functional areas, such as sales and marketing management, customer relationship management (CRM), financial management, inventory management, category management, and so on. Decision support systems collect and transform data from these various data sources into more meaningful and understandable information to end-users.
A major goal of decision support systems is to provide end-users with results to business questions quickly and accurately. Business questions may be translated to “queries” by a query server, and the queries are then “run” against databases. Depending on the complexity of the queries, a long time may be required by the servers for these databases to return results to the queries. In general, it is desirable to be able to return the results to the end-users as fast as possible.
The processing of queries consumes large amounts of resources at the query and database servers and the computer network that interconnects these servers. The query server normally parses each query received from an end-user into “physical” queries against each database where data for the final results may be stored. The query server would then receive intermediate results from all queried databases and perform any required post-processing to obtain the final results.
Query caching may be used to improve performance by avoiding unnecessary processing. With query caching, the results of prior queries are stored in a local cache, which may be implemented on a storage unit (e.g., a memory unit or a disk drive) that can be more quickly and easily accessed by the query server. If a new query is subsequently received and can use the results stored in the cache, then the database processing for the new query can be avoided. This may then result in a dramatic improvement in the average response time for queries. Besides faster response time, the ability to answer a new query from a local cache conserves resources at (1) the query server, since post processing on the intermediate results received from queried databases may be avoided, (2) the database server, which may then be able to perform other processing, and (3) the network, since intermediate results do not have to be sent over the network to the query server.
The effectiveness of query caching is dependent on the ability to determine whether or not the results for queries that have been saved in the cache (i.e., cached queries) may be used to obtain the results for a new query. In the simple case in which a new query is exactly like one of the cached queries, the results for this cached query may be quickly retrieved and presented to the end-user. However, in many instances, the new query will not be exactly like any of the cached queries.
A major challenge with query caching is then the ability to determine whether or not results for a new query may be obtained from results for a cached query. This will be possible if the new query is a subset of and “subsumed” by the cached query. A cache hit may be declared if the new query can be answered by the cached query, and a cache miss may be declared otherwise.
In one conventional scheme for determining whether or not a new query can be answered by a cached query, the new query is evaluated against each cached query. This scheme provides acceptable performance when the number of cached queries is small (e.g., tens of cached queries), but would be ineffective when the number of cached queries is large (e.g., hundreds or thousands of cached queries).
The determination of whether or not a new query is subsumed by a cached query is also made more challenging by the fact that queries often ask for “aggregated” data, which is data obtained by operating on multiple data entries. For example, a query may ask for the sum of all revenues for each year, which may then be obtained by summing the revenues for all transactions of each year. In this example, “transactions” would be the data entries and “sum” is the aggregation being performed on the data entries. In the process of aggregating data, the value of each individual data entry is lost (i.e., the value of each transaction is not available, in the above example).
Conventionally, for a new query with one or more aggregates to be considered subsumed by a cached query, the aggregates of the new query are required to exactly match the aggregates of the cached query or fall within a very limited range of exceptions. This strict aggregate matching criterion can often result in declaration of a cache miss when in fact the results for the new query may be obtained from the results from the cached query. The ability to detect cache hits may be even more important for queries with aggregates because additional savings may be achieved from not having to perform the aggregation.
As can be seen, techniques that can be used to improve query caching in the presence of aggregates are highly desirable.